package wtx.geeks;

import java.util.Arrays;
import java.util.Random;
import java.util.StringJoiner;

/**
 * https://practice.geeksforgeeks.org/problems/smallest-positive-missing-number/1
 * 看hints，居然是用array index 
 */
public final class MissingPos {
  public static int missingNumberBrute(int arr[], int size) {
    Arrays.sort(arr);
    if (arr[0] > 1) {
      return 1;
    }
    int ret = arr[size-1] + 1;
    for (int i = 1; i < size; ++i) {
      if (arr[i] > 1 && arr[i - 1] < 0) {
        ret = 1;
        break;
      }
      if (arr[i - 1] >= 0 && arr[i] - arr[i - 1] > 1) {
        ret = arr[i - 1] + 1;
        break;
      }
    }
    return ret;
  }

  public static int missingNumber(int arr[], int size) {
    // 通过分治算法，估计可以实现期望时间复杂度O(n)
    final int ZERO = 0;
    int i = 0, j = size-1;
    for (; i < j && i < size;) {
      while(arr[i] < ZERO) {
        ++i;
      }
      swap(arr, i, j--);
    }
    if (arr[i] < ZERO) {
      ++i;
    }
    if (i == size) {
      return 1;
    }
    int ret = missingNumberHalf(arr, i, size);
    if (arr[i] > 1) {
      return 1;
    } else {
      return ret;
    }
  }

  private static int missingNumberHalf(int arr[], int left, int right) {
    if (left == right) {
      System.err.println("size less than 1!");
      return 1;
    }
    if (right - left <= 1) {
      return arr[left] + 1;
    }
    if (right - left == 2) {
      if (arr[right - 1] < arr[left]) {
        swap(arr, left, right - 1);
      }
      int ret = arr[left] + 1;
      if (ret != arr[right - 1]) {
        return ret;
      } else {
        return ret + 1;
      }
    }
    // pivot and swap
    int mid = (left + right) / 2;
    int pivot = arr[mid];
    if (arr[left] > arr[right - 1]) {
      swap(arr, left, right - 1);
    }
    if (arr[left] > pivot) {
      swap(arr, left, mid);
    }
    if (arr[right - 1] < pivot) {
      swap(arr, mid, right - 1);
    }
    pivot = arr[mid];
    int minv = Integer.MAX_VALUE, maxv = pivot;
    int maxvLessPivot = Integer.MIN_VALUE;
    swap(arr, right-1, mid);
    int i = left, j = right - 1; 
    for (;i < j;) {
      while (i < j && arr[i] < pivot) {
        if (arr[i] < minv) {
          minv = arr[i];
        }
        if (arr[i] > maxvLessPivot) {
          maxvLessPivot = arr[i];
        } 
        ++i;
      }
      if (i >= j) {
        break;
      }
      swap(arr, i, --j);
      if (arr[j] > maxv) {
        maxv = arr[j];
      }
    }
    mid = i;
    swap(arr, right-1, mid); 
    if (mid == left) {
      mid = left + 1;
      minv = maxvLessPivot = arr[left];
    }
    // merge
    int leftMiss = missingNumberHalf(arr, left, mid);
    arr[left] = minv;
    arr[mid - 1] = maxvLessPivot;
    maxv = arr[mid-1];
    if (maxv > leftMiss) {
      return leftMiss;
    } 
    if (right == mid) {
      mid = mid - 1; 
      pivot = maxv = arr[mid];
    }
    int rightMiss = missingNumberHalf(arr, mid, right);
    arr[mid] = pivot;
    arr[right - 1] = maxv;
    int minv2 = arr[mid];
    if (leftMiss < minv2) {
      return leftMiss;
    } else {
      // must be leftMiss == minv2
      return rightMiss;
    }
  }

  // public static int missingNumber(int arr[], int size) {
  // int lp = 1;
  // int rp = Integer.MAX_VALUE;
  // // int last_pos_rp = size - 1;
  // int i = 0, j = size - 1;
  // while(i < j) {
  // if (arr[i] < lp) {
  // ++i;
  // } else if (arr[i] == lp) {
  // lp = arr[i] + 1;
  // ++i;
  // if (lp == rp) {
  // // reset rp
  // rp = Integer.MAX_VALUE;
  // j = size - 1;
  // }
  // } else if (arr[i] < rp) {
  // // last_pos_rp = j;
  // rp = arr[i];
  // swap(arr, i, j--);
  // } else {
  // swap(arr, i, j--);
  // }
  // }
  // return lp;
  // }
  private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  }

  /**
   * Says hello to the world.
   * 
   * @param args
   *               The arguments of the program.
   */
  public static void main(String[] args) {
    Random rnd = new Random(17334);
    for (int i = 0; i < 100; ++i) {
      final int arrLen = rnd.nextInt(20) + 5;
      int[] arr = new int[arrLen];
      StringJoiner sj = new StringJoiner(", ", "{", "}");
      for (int j = 0; j < arrLen; ++j) {
        arr[j] = rnd.nextInt(20) - 10;
        sj.add("" + arr[j]);
      }
      int[] arr2 = new int[arrLen];
      System.arraycopy(arr, 0, arr2, 0, arrLen);
      System.out.println("origin array: " + sj.toString());
      int mis = missingNumber(arr, arrLen);
      int mis0 = missingNumberBrute(arr2, arrLen);
      sj = new StringJoiner(", ", "{", "}");
      for (int e : arr2) {
        sj.add("" + e);
      }
      System.out.println(String.format("sorted array = %s, \nmis = (%d, %d)", sj.toString(), mis, mis0));
      if (mis != mis0) {
        System.out.println("    Failed! ");
        return;
      }
    }
  }
}
